class code3 {
    //最小覆盖子串:滑动窗口+hash+dif==0
    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();

        //不满足
        if(m < n) return "";

        int[] count = new int[128];
        int dif = 0;
        for(int i=0;i<n;i++) {
            count[t.charAt(i)-'A']++;
            count[s.charAt(i)-'A']--;
        }
        for(int val : count) {
            if(val > 0) dif++;
        }
        //直接一样出结果
        if(dif == 0) return s.substring(0,n);

        int l=0,r=n;
        int lmin=0,rmin=m;
        for(;r<m;r++) {
            //进窗口
            count[s.charAt(r)-'A']--;
            if(count[s.charAt(r)-'A']==0) dif--;
            //t还没完全覆盖
            if(dif!=0) continue;
            //判断
            while(dif==0) {
                //出窗口
                count[s.charAt(l)-'A']++;
                if(count[s.charAt(l)-'A'] > 0) dif++;
                l++;
            }
            //更新结果
            if(r-l+1 < rmin-lmin) {
                lmin = l-1;
                rmin = r;
            }
        }
        return rmin == m ? "" :s.substring(lmin, rmin + 1);
    }
}